package com.zengqingfa.algorithm.cz.chapter02;

import java.util.Arrays;

/**
 * @author zengqingfa
 * @className MergeSort
 * @description 归并排序
 * @create 2021/8/23 20:54
 */
public class MergeSort {

    /**
     * 归并所需要的辅助数组
     */
    private static Comparable[] assits;

    public static void main(String[] args) {
        Integer[] arr={8,4,5,7,1,3,6,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void sort(Comparable[] arr) {
        assits = new Comparable[arr.length];
        int lo = 0;
        int hi = arr.length - 1;
        sort(arr, lo, hi);
    }

    /**
     * 对数组arr中从lo到high排序
     *
     * @param arr
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //对lo到mid之间的元素排序
        sort(arr, lo, mid);
        //对mid+1到hi之间的元素排序
        sort(arr, mid + 1, hi);
        //对lo到mid 和mid+1到hi两组数据进行合并
        merge(arr, lo, mid, hi);
    }

    /**
     * 合并数组
     *
     * @param arr
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] arr, int lo, int mid, int hi) {
        //lo到mid这组数据和mid+1到hi这组数据归并到辅助数组assist对应的索引处
        //i 指向辅助索引的第一个位置
        int i = lo;
        //指向第一组元素的第一个位置
        int p1 = lo;
        //指向第二组元素的第一个位置
        int p2 = mid + 1;
        //比较左边小组和右边小组中的元素大小，哪个小，就把哪个数据填充到assist数组中
        while (p1 <= mid && p2 <= hi) {
            if (less(arr[p1], arr[p2])) {
                assits[i++] = arr[p1++];
            } else {
                assits[i++] = arr[p2++];
            }
        }
        //上面的循环结束后，如果退出循环的条件是p1<=mid，则证明左边小组中的数据已经归并完毕，
        // 如果退 出循环的条件是p2<=hi,则证明右边小组的数据已经填充完毕；
        // 所以需要把未填充完毕的数据继续填充到assist中,
        // 下面两个循环，只会执行其中的一个
        while (p2 <= hi) {
            assits[i++] = arr[p2++];
        }

        while (p1 <= mid) {
            assits[i++] = arr[p1++];
        }

        //数组从lo到hi中的元素是有序的
        for (int j = lo; j <= hi; j++) {
            arr[j] = assits[j];
        }
    }

    /**
     * 判断a是否比b小
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组arr中索引i和j处的元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}